Once you have a binary tree holding an alphabetically sorted list or a parse tree, you may wish to print it out. But what order should you print the nodes in? There are three orderings: inorder, postorder, and preorder.
Instead of thinking of the entire tree all at once, think of a single node. Instead of thinking of the node as having two children, think of it as having two TREES as children. If one or both of the children are missing, think of it as an empty tree.
Now we can describe the order in which we will move through a tree by describing in what order we print the three parts of the tree: the root, and the two subtrees. Say we print first the root, then the left subtree, then the right. How do we print a subtree? The same way: print ITS root, its left
Before I give an example, let me state the three orders:
Inorder: print the left subtree, the node, then the right subtree.
Postorder: print the left subtree, the right subtree, the node itself.
Preorder: print the node, then the left subtree, then the right.
Suppose you are printing a small tree in preorder. First you print the root. Now print the left subtree; say it is just a single node. We print the left subtree of this node (nothing), then the node, then its right subtree (nothing). Now we print the right subtree of the top (root) node. Suppose that is a node with two children. Applying preorder, we print the node, then its left then right child.
The trick is, to print out a subtree, shut every other part of the tree out of your mind and apply the rules to the subtree just as you did to its parent. And surprise: when you print an alphabetical search tree in inorder, you get an alphabetical list of its items!
When you print a parse tree in inorder, postorder, or preorder, you get (respectively) an infix, postfix, or prefix expression! Note, though, that the infix expression will be missing all parentheses, which may be a significant omission. But the postorder and preorder traversals, if typed back in and parsed, are guaranteed to recreate the same tree.
Note that in real life, you aren't usually traversing a tree just to print it out. You traverse the tree in the same order, but instead of printing each node's contents, you perform some action on the node. All three traversals insure that each node is acted on once and only once.
